package org.basis.algorithm.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * 随机获取 池
 * 【题目】
 * 设计一种结构，在该结构中有如下三个功能:
 * insert(key):将某个key加入到该结构，做到不重复加入
 * delete(key):将原本在结构中的某个key移除
 * getRandom(): 等概率随机返回结构中的任何一个key。
 * 【要求】 Insert、delete和getRandom方法的时间复杂度都是O(1)
 *
 * @author Mr_wenpan@163.com 2022/01/04 15:14
 */
public class RandomPool {

    public static class Pool<K> {

        /**
         * 存放key和index的map
         */
        Map<K, Integer> keyIndexMap;
        /**
         * 存放index和key的map
         */
        Map<Integer, K> indexKeyMap;
        /**
         * 索引大小
         */
        int size;

        public Pool() {
            size = 0;
            keyIndexMap = new HashMap<>();
            indexKeyMap = new HashMap<>();
        }

        public void insert(K key) {
            // 已经存在于集合中则不用添加
            if (keyIndexMap.containsKey(key)) {
                return;
            }
            keyIndexMap.put(key, size);
            indexKeyMap.put(size++, key);
        }

        /**
         * 等概率随机获取一个位置的key
         */
        public K getRandom() {
            // 产生一个随机数，这里使用Math.random()函数来保证随机性一定是等概率的
            int random = (int) (Math.random() * size);
            // 根据随机数获取到一个key
            return indexKeyMap.get(random);
        }

        /**
         * 根据key删除数据，保证删除后仍然可以通过getRandom等概率的随机获取key
         */
        public void delete(K key) {
            // 通过key获取到要删除的key对应的索引
            Integer deleteIndex = keyIndexMap.get(key);
            if (deleteIndex == null) {
                return;
            }
            Integer lastIndex = --size;
            // 用最后一条数据来填漏洞
            K last = indexKeyMap.get(lastIndex);
            keyIndexMap.put(last, deleteIndex);
            indexKeyMap.put(deleteIndex, last);
            // 删除最后一个key
            indexKeyMap.remove(lastIndex);
            keyIndexMap.remove(key);
        }

    }
}
